package Offer;

/**
 * 反转链表
 * @author 是阿秋啊
 * @date 2022/03/29 19:59
 **/
public class Num24 {
    public ListNode reverseList(ListNode head) {
        // 递归
//        if (head == null || head.next == null) {
//            return head;
//        }
//        // 保存下一节点
//        ListNode sec = head.next;
//        // 新的头节点，为头节点的下一节点
//        ListNode newHead = reverseList(sec);
//        // 让头节点的下一个节点指向头节点
//        sec.next = head;
//        // 头节点下一节点置空
//        head.next = null;
//        return newHead;
        // 头插法
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode dummyHead = new ListNode(-1);
//        while (head != null) {
//            ListNode node = new ListNode(head.val);
//            node.next = dummyHead.next;
//            dummyHead.next = node;
//            head = head.next;
//        }
//        return dummyHead.next;
        // 原地移动法
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}
